﻿﻿#define  _CRT_SECURE_NO_WARNINGS 1

#include "List.h"

/*
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
*/

struct ListNode
{
	int val;
	struct ListNode* next;
};

struct ListNode* detectCycle(struct ListNode* head)
{
	struct ListNode* slow = head, * fast = head;
	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
		//推导的结论一个指针从相遇点开始走，一个指针从head走，他们会在入口点相遇
		if (slow == fast)
		{
			struct ListNode* meet = slow;
			while (head != meet)
			{
				head = head->next;
				meet = meet->next;
			}
			return meet;
		}
	}
	return NULL;
}